package homework;

import javax.naming.InsufficientResourcesException;
import javax.swing.*;
import java.util.*;

//作业标题(2713)
//前k个高频单词
//
//作业内容
//前k个高频单词
//https://leetcode.cn/problems/top-k-frequent-words/description/
public class h2713 {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for(String word : words)
        {
            if(map.containsKey(word))
            {
                map.put(word, map.get(word) + 1);
            }
            else {
                map.put(word, 1);
            }
        }

        PriorityQueue<Map.Entry<String, Integer>> priorityQueue = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0)
                {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        for(Map.Entry<String, Integer> entry : map.entrySet())
        {
            if(priorityQueue.size() < k)
            {
                priorityQueue.offer(entry);
            }
            else
            {
                Map.Entry<String, Integer> top = priorityQueue.peek();
                if(top.getValue().compareTo(entry.getValue()) < 0)
                {
                    priorityQueue.poll();
                    priorityQueue.offer(entry);
                }
                else if(top.getValue().compareTo(entry.getValue()) == 0 && top.getKey().compareTo(entry.getKey()) > 0)
                {
                    priorityQueue.poll();
                    priorityQueue.offer(entry);
                }
            }
        }

        List<String> ret = new ArrayList<>();
        while (!priorityQueue.isEmpty())
        {
            ret.add(priorityQueue.poll().getKey());
        }
        Collections.reverse(ret);
        return ret;
    }
}
